package 数据结构.章节10._168_实现HashMap;

import java.util.Iterator;

/**
 * @author 挚爱之夕
 * @date 2021/10/15 - 10 - 15 - 20:14
 * @Description: 数据结构.章节10._168_实现HashMap
 * @Version: 1.0
 */
public class MyHashMap<K, V> implements IMap<K, V> {
    //桶的数量
    private final int length = 16;
    //桶本质是链表
    private final Node<K, V>[] buckets = new Node[length];
    //表中元素数量
    private static int size = 0;

    @Override
    public void clear() {
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = null;
        }
        size = 0;
    }

    @Override
    public boolean containsKey(K key) {
        //找桶号
        int index = hash1(key);
        if (buckets[index] != null) {
            Node<K, V> p = buckets[index];
            while (p != null) {
                if (key == p.key || (p.key.hashCode() == key.hashCode() && p.key.equals(key))) {
                    return true;
                }
                p = p.next;
            }
        }
        return false;
    }

    @Override
    public boolean containsValue(V value) {
        //遍历桶
        for (Node<K, V> bucket : buckets) {
            Node<K, V> p = bucket;
            while (p != null) {
                if (p.value == value || (p.value.hashCode() == value.hashCode() && p.value.equals(value))) {
                    return true;
                }
                p = p.next;
            }
        }
        return false;
    }

    @Override
    public V get(K key) {
        //找桶号
        int index = hash1(key);
        //该桶没有节点
        if (buckets[index] == null)
            return null;
        else {
            //表头
            Node<K, V> p = buckets[index];
            while (p != null) {
                if (p.key == key || (p.key.hashCode() == key.hashCode() && p.key.equals(key)))
                    return p.value;
                p = p.next;
            }
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public K[] keySet() {
        if (size() == 0)
            return null;
        else {
            K[] res = (K[]) (new Object[size]);
            int cur = 0;
            for (Node<K, V> node : buckets
            ) {
                Node<K, V> p = node;
                while (p != null) {
                    res[cur++] = p.key;
                    p = p.next;
                }
            }
            return res;
        }
    }

    @Override
    public V[] valueSet() {
        if (size() == 0)
            return null;
        else {
            V[] res = (V[]) new Object[size];
            int cur = 0;
            for (Node<K, V> node : buckets
            ) {
                Node<K, V> p = node;
                while (p != null) {
                    res[cur++] = p.value;
                    p = p.next;
                }
            }
            return res;
        }
    }

    @Override
    public void put(K key, V value) {
        Node<K, V> node = new Node<>(key, value);
        int index = hash1(key);
        //桶内链表还未创建
        if (buckets[index] == null) {
            buckets[index] = node;
            size++;
        } else {
            Node<K, V> p = buckets[index];
            while (p != null) {
                K k1 = p.key;
                //重复的key
                if (key == k1 || (key.hashCode() == k1.hashCode() && key.equals(k1))) {
                    p.value = value;    //存在相同的key，更新value
                    break;
                }
                //已经是最后一个节点，放在该节点之后
                if (p.next == null) {
                    p.next = node;
                    size++;
                    break;
                }
                p = p.next;
            }
        }

    }

    //根据key返回一个hash值，对应桶号
    private int hash1(K key) {
        //取余：返回范围[0,length-1]
        return key.hashCode() % length;
    }

    @Override
    public void putAll(IMap<? extends K, ? extends V> map) {

    }

    @Override
    public V remove(K key) {
        //找桶号
        int index = hash1(key);
        if (buckets[index] == null)
            return null;
        else {
            //当前节点
            Node<K, V> p = buckets[index];
            //上一个节点
            Node<K, V> pre = p;
            while (p != null) {
                //发现key
                if (p.key == key || (p.key.hashCode() == key.hashCode() && p.key.equals(key))) {
                    if (p == pre) {//位于头结点
                        buckets[index] = p.next;
                    } else {
                        pre.next = p.next;
                        p.next = null;
                    }
                    size--;
                    return p.value;
                }
                pre = p;
                p = p.next;
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    //比较器
    @Override
    public Iterator<Node> iterator() {
        return new Iterator<Node>() {
            int i = 0;
            Node<K, V> p = buckets[0];

            @Override
            public boolean hasNext() {
                while (i < length && p == null) {
                    i++;
                    if (i == length)
                        p = null;
                    else
                        p = buckets[i];
                }
                return p != null;
            }

            @Override
            public Node<K, V> next() {
                Node<K, V> res = p;
                p = p.next;
                return res;
            }
        };
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < buckets.length; i++) {
            Node<K, V> p = buckets[i];
            while (p != null) {
                sb.append("(").append(p.key).append(", ").append(p.value).append("),");
                p = p.next;
            }
        }
        if (sb.charAt(sb.length() - 1) == ',') {
            sb = new StringBuilder(sb.substring(0, sb.length() - 1));
        }
        sb.append("]");
        return sb.toString();
    }
}
